package 回溯;

import java.util.Arrays;

public class NQueue {
	
	public static int solution(int N) {
		int chessBoard [][] = new int [N][N];
		int ans = process(0,chessBoard,N);
//		for(int arr[] : chessBoard)
//			System.out.println(Arrays.toString(arr));
		return ans;
	}
	
	// index 表示 行 ,  而  i 表示 列
	public static int process(int index,int [][]chessBoard,int N) {
		if(index == N)
			return 1;
		int ans = 0;
		for(int i = 0; i < N;i++ )  {
			if(check(index,i,chessBoard)) {
				chessBoard[index][i] = 1;
				ans += process(index + 1,chessBoard,N);
				chessBoard[index][i] = 0;
			}
		}
		return ans;
	}
	public static boolean check(int row,int column, int [][] chessBoard) {
		int N = chessBoard.length; 
		// 判断 有没有同一行的
//		for(int i = column; i >= 0 ;i--) {
//			if(chessBoard[i][column] == 1)
//				return false;
//		}
		//判断有没有  同一列的
		for(int i = row; i >= 0 ;i--) {
			if(chessBoard[i][column] == 1)
				return false;
		}
		
		// 判断有没有同一对角线的
		for(int i = row ,j = column; i >= 0 && j >= 0 ;j-- ,i--) {
			if(chessBoard[i][j] == 1)
				return false;
		}
		for(int i = row ,j = column; i >= 0 && j < N ;j++ ,i--) {
			if(chessBoard[i][j] == 1)
				return false;
		}
		return true;
	}
	
	public static void main(String []args) {
		System.out.println(solution(8));
	}
}
